package practice;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Stack;

public class Day29 {
    private ArrayList<Integer> function(String s, int index) {
        Stack<Integer> stack = new Stack<>();
        char op = '+';
        int i = index;
        int num = 0;
        while (i < s.length()) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                num = num * 10 + s.charAt(i) - '0';
                System.out.println("num: " + num);
                if (i < s.length() - 1) {
                    i++;
                    continue;
                }
            }
            if (s.charAt(i) == '(') {
                //遇到一个(，意味着需要后面是一个完成的计算
                ArrayList<Integer> ret = function(s, i + 1);
                num = ret.get(0);
                i = ret.get(1);
                if (i < s.length() - 1) {
                    i++;
                    continue;
                }
            }
            if (op == '+') {
                stack.push(num);
            } else if (op == '-') {
                stack.push(-num);
            } else if (op == '*') {
                stack.push(stack.pop() * num);
            }
            if (s.charAt(i) == ')') {
                break;
            } else {
                op = s.charAt(i);
            }
            num = 0;
            i++;
        }
        int sum = 0;
        while (!stack.isEmpty()) {
            sum += stack.pop();
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(sum);
        list.add(i);
        return list;
    }
    public int solve (String s) {
        return function(s, 0).get(0);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        return (getMid(nums1,0,n-1,nums2,0,m-1,(n+m+1)/2) + getMid(nums1,0,n-1,nums2,0,m-1,(n+m+2)/2)) * 0.5;
    }

    private int getMid(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k) {
        int len1 = end1-start1+1;
        int len2 = end2-start2+1;
        //保证nums1是长度小的，nums2是长度大的
        if(len1 > len2) {
            return getMid(nums2,start2,end2,nums1,start1,end1,k);
        }
        //否则就是len1<len2，但是有可能len1为0
        if(len1 == 0) {
            return nums2[start2+k-1];
        }
        //循环结束条件
        if(k == 1) {
            return Math.min(nums1[start1],nums2[start2]);
        }

        //k==1之前的二分查找的过程
        int i = start1 + Math.min(len1,k/2)-1;
        int j = start2 + Math.min(len2,k/2) - 1;
        if(nums1[i] > nums2[j]) {
            return getMid(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }else {
            return getMid(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }
    }

    //变成一颗高度平衡的二叉搜素数（每次取中点，然后构建左子树和右子树）
    public TreeNode sortedArrayToBST(int[] nums) {
        //其实该题就是构建二叉树
        return sortedTree(nums,0,nums.length-1);
    }
    private TreeNode sortedTree(int[] nums, int left, int right) {
        if(left > right) {
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        root.left = sortedTree(nums,left,mid-1);
        root.right = sortedTree(nums,mid+1,right);
        return root;
    }

    //找出字符串中第一个匹配项的下标
    public int strStr(String haystack, String needle) {
        char ch = needle.charAt(0);
        int i = 0;
        while(i < haystack.length()) {
            if(ch == haystack.charAt(i)) {
                //向后判断是否整个相等
                int j = i + 1;
                int k = 1;
                while(j < haystack.length() && k < needle.length()) {
                    if(haystack.charAt(j) != needle.charAt(k)) {
                        break;
                    }
                    j++;
                    k++;
                }
                if(k >= needle.length()) {
                    return i;
                }
            }
            i++;
        }
        return -1;
    }

    //判断子序列
    public boolean isSubsequence(String s, String t) {
        if(s.length() == 0) {
            return true;
        }
        int left1 = 0;
        int left2 = 0;
        while(left1 < t.length()) {
            if(left2 >= s.length()) {
                return true;
            }
            if(s.charAt(left2) == t.charAt(left1)) {
                left1++;
                left2++;
            }else {
                left1++;
            }
        }
        if(left2 >= s.length()) {
            return true;
        }
        return false;
    }
}
